<html lang="zh-CN"><head><meta charset="UTF-8"><style>.nodata  main {width:1000px;margin: auto;}</style></head><body class="nodata " style=""><div class="main_father clearfix d-flex justify-content-center " style="height:100%;"> <div class="container clearfix " id="mainBox"><main><div class="blog-content-box">
<div class="article-header-box">
<div class="article-header">
<div class="article-title-box">
<h1 class="title-article" id="articleContentId">(C卷,100分)- 找出经过特定点的路径长度（Java & JS & Python）</h1>
</div>
</div>
</div>
<div id="blogHuaweiyunAdvert"></div>

        <div id="article_content" class="article_content clearfix">
        <link rel="stylesheet" href="https://csdnimg.cn/release/blogv2/dist/mdeditor/css/editerView/kdoc_html_views-1a98987dfd.css">
        <link rel="stylesheet" href="https://csdnimg.cn/release/blogv2/dist/mdeditor/css/editerView/ck_htmledit_views-044f2cf1dc.css">
                <div id="content_views" class="htmledit_views">
                    <h4 id="main-toc">题目描述</h4> 
<p>无</p> 
<p></p> 
<h4 id="%E8%BE%93%E5%85%A5%E6%8F%8F%E8%BF%B0">输入描述</h4> 
<p>输入一个字符串&#xff0c;都是以大写字母组成&#xff0c;每个相邻的距离是 1&#xff0c;</p> 
<p>第二行输入一个字符串&#xff0c;表示必过的点。</p> 
<p>说明每个点可过多次。</p> 
<p></p> 
<h4 id="%E8%BE%93%E5%87%BA%E6%8F%8F%E8%BF%B0">输出描述</h4> 
<p>经过这些必过点的最小距离是多少</p> 
<p></p> 
<h4 id="%E7%94%A8%E4%BE%8B">用例</h4> 
<table border="1" cellpadding="1" cellspacing="1" style="width:500px;"><tbody><tr><td style="width:86px;">输入</td><td style="width:412px;"> <p>ANTSEDXQOKPUVGIFWHJLYMCRZB<br /> ABC</p> </td></tr><tr><td style="width:86px;">输出</td><td style="width:412px;">28</td></tr><tr><td style="width:86px;">说明</td><td style="width:412px;">无</td></tr></tbody></table> 
<p></p> 
<h4 id="%E9%A2%98%E7%9B%AE%E8%A7%A3%E6%9E%90">题目解析</h4> 
<p>感觉本题题目描述太简略了&#xff0c;缺少很多关键信息。</p> 
<ul><li>第一行输入的字符串中是否有重复字母&#xff1f;</li><li>第二行输入的字符串中是否有重复字母&#xff1f;</li><li>运动起点在哪&#xff1f;一定是第一行第一个字母吗&#xff1f;&#xff08;给出的用例无法解答该问题&#xff09;</li><li>运动方向变更逻辑是啥&#xff1f;随意变更&#xff0c;还是必须到达终点后折返&#xff1f;&#xff08;给出的用例无法解答该问题&#xff09;</li><li>每个点可过多次&#xff0c;那么是否可以原地走&#xff1f;</li></ul> 
<p>因为题目没有这些关键信息&#xff0c;因此这道题目的难度就不确定了。</p> 
<p>我是这样考虑的&#xff1a;</p> 
<ul><li>第一行和第二行都可能出现重复字母</li><li>运动起点必须从第一行输入的第一个字母开始</li><li>运动方向可以随意变更</li><li>允许原地走</li></ul> 
<p>这样的话&#xff0c;经过必过点的路径才能多样化&#xff0c;才有最小距离概念。</p> 
<p></p> 
<p>解题思路如下&#xff0c;首先统计第二行输入的必过点在第一行字符串中的索引位置&#xff0c;需要注意的是必过点可能在第一行中出现多次&#xff0c;我们都要统计到。</p> 
<p>下面算法中&#xff0c;我们用points保存必过点信息&#xff0c;idxs保存必过点的索引信息。</p> 
<p>接下来&#xff0c;通过dfs求解经过必过点的所有的可能路径。</p> 
<p>之后计算这些路径的距离&#xff0c;即相邻两点求差绝对值&#xff0c;然后相加&#xff0c;需要注意的时&#xff0c;我们需要将从起点走到第一个必过点的距离也加入为路径距离。</p> 
<p>然后&#xff0c;对所有路径距离进行排序&#xff0c;最小的就是题解。</p> 
<p></p> 
<p>自测用例&#xff1a;</p> 
<p>ANTSEDXQOKPUVGIFWHJLYMCRZB<br /> GUYA </p> 
<p><img alt="" height="216" src="https://img-blog.csdnimg.cn/30ba7c6541c64a50a65e9530ddd678c0.png" width="1139" /></p> 
<p>最小距离44&#xff08;注意&#xff0c;该最小距离是&#xff0c;必须从第一行输入的首字母出发的最小距离&#xff09;</p> 
<p></p> 
<p>ANTSEDXQOKPUVGIFWHUJLYMCRZ<br /> GUYA</p> 
<p><img alt="" height="241" src="https://img-blog.csdnimg.cn/19bff82d9c764cd5b96ec847c3cf1717.png" width="1088" /></p> 
<p> 发现有两条路径</p> 
<p>绿色路径更短&#xff0c;最小距离42&#xff08;注意&#xff0c;该最小距离是&#xff0c;必须从第一行输入的首字母出发的最小距离&#xff09;</p> 
<p></p> 
<h4 id="%E7%AE%97%E6%B3%95%E6%BA%90%E7%A0%81">JS算法源码</h4> 
<pre><code class="language-javascript">/* JavaScript Node ACM模式 控制台输入获取 */
const readline &#61; require(&#34;readline&#34;);

const rl &#61; readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

const lines &#61; [];
rl.on(&#34;line&#34;, (line) &#61;&gt; {
  lines.push(line);

  if (lines.length &#61;&#61; 2) {
    console.log(getResult(lines[0], lines[1]));
    lines.length &#61; 0;
  }
});

function getResult(all, must) {
  const mustCharIdx &#61; {};
  const mustCharSet &#61; new Set(must);

  for (let i &#61; 0; i &lt; all.length; i&#43;&#43;) {
    const c &#61; all[i];
    if (mustCharSet.has(c)) {
      mustCharIdx[c] ? mustCharIdx[c].push(i) : (mustCharIdx[c] &#61; [i]);
    }
  }

  const ans &#61; [Infinity];
  dfs(0, must, mustCharIdx, [], ans);
  return ans[0];
}

function dfs(index, must, mustCharIdx, path, ans) {
  if (path.length &#61;&#61; must.length) {
    let dis &#61; path[0]; // 运动起点必须从第一行输入all的第一个字母开始
    // let dis &#61; 0; // 运动起点从all中must第一个字母位置开始

    for (let i &#61; 1; i &lt; path.length; i&#43;&#43;) {
      dis &#43;&#61; Math.abs(path[i] - path[i - 1]);
    }

    ans[0] &#61; Math.min(ans[0], dis);
    return;
  }

  for (let idx of mustCharIdx[must[index]]) {
    path.push(idx);
    dfs(index &#43; 1, must, mustCharIdx, path, ans);
    path.pop();
  }
}
</code></pre> 
<p></p> 
<h4>Java算法源码</h4> 
<pre><code class="language-java">import java.util.*;

public class Main {
  public static void main(String[] args) {
    Scanner sc &#61; new Scanner(System.in);

    String all &#61; sc.next();
    String must &#61; sc.next();

    System.out.println(getResult(all, must));
  }

  public static int getResult(String all, String must) {
    HashMap&lt;Character, ArrayList&lt;Integer&gt;&gt; mustCharIdx &#61; new HashMap&lt;&gt;();

    HashSet&lt;Character&gt; mustChar &#61; new HashSet&lt;&gt;();
    for (char c : must.toCharArray()) {
      mustChar.add(c);
    }

    for (int i &#61; 0; i &lt; all.length(); i&#43;&#43;) {
      char c &#61; all.charAt(i);
      if (mustChar.contains(c)) {
        mustCharIdx.putIfAbsent(c, new ArrayList&lt;&gt;());
        mustCharIdx.get(c).add(i);
      }
    }

    int[] ans &#61; {Integer.MAX_VALUE};
    dfs(0, must, mustCharIdx, new LinkedList&lt;&gt;(), ans);
    return ans[0];
  }

  public static void dfs(
      int index,
      String must,
      HashMap&lt;Character, ArrayList&lt;Integer&gt;&gt; mustCharIdx,
      LinkedList&lt;Integer&gt; path,
      int[] ans) {
    if (path.size() &#61;&#61; must.length()) {
      int dis &#61; path.get(0); // 运动起点必须从第一行输入all的第一个字母开始
      // int dis &#61; 0; // 运动起点从all中must第一个字母位置开始
      for (int i &#61; 1; i &lt; path.size(); i&#43;&#43;) {
        dis &#43;&#61; Math.abs(path.get(i) - path.get(i - 1));
      }
      ans[0] &#61; Math.min(ans[0], dis);
      return;
    }

    for (Integer idx : mustCharIdx.get(must.charAt(index))) {
      path.add(idx);
      dfs(index &#43; 1, must, mustCharIdx, path, ans);
      path.removeLast();
    }
  }
}
</code></pre> 
<p></p> 
<h4>Python算法源码</h4> 
<pre><code class="language-python">import sys

# 输入获取
all &#61; input()
must &#61; input()


def dfs(index, must, mustCharIdx, path, ans):
    if len(path) &#61;&#61; len(must):
        dis &#61; path[0]  # 运动起点必须从第一行输入all的第一个字母开始
        # dis &#61; 0  # 运动起点从all中must第一个字母位置开始

        for i in range(1, len(path)):
            dis &#43;&#61; abs(path[i] - path[i - 1])

        ans[0] &#61; min(ans[0], dis)
        return

    for idx in mustCharIdx[must[index]]:
        path.append(idx)
        dfs(index &#43; 1, must, mustCharIdx, path, ans)
        path.pop()


def getResult(all, must):
    mustCharIdx &#61; {}

    mustChar &#61; set(must)

    for i in range(len(all)):
        c &#61; all[i]

        if c in mustChar:
            if mustCharIdx.get(c) is None:
                mustCharIdx[c] &#61; []
            mustCharIdx[c].append(i)

    ans &#61; [sys.maxsize]
    dfs(0, must, mustCharIdx, [], ans)
    return ans[0]


print(getResult(all, must))</code></pre> 
<p></p>
                </div>
        </div>
        <div id="treeSkill"></div>
        <div id="blogExtensionBox" style="width:400px;margin:auto;margin-top:12px" class="blog-extension-box"></div>
    <script>
  $(function() {
    setTimeout(function () {
      var mathcodeList = document.querySelectorAll('.htmledit_views img.mathcode');
      if (mathcodeList.length > 0) {
        for (let i = 0; i < mathcodeList.length; i++) {
          if (mathcodeList[i].naturalWidth === 0 || mathcodeList[i].naturalHeight === 0) {
            var alt = mathcodeList[i].alt;
            alt = '\\(' + alt + '\\)';
            var curSpan = $('<span class="img-codecogs"></span>');
            curSpan.text(alt);
            $(mathcodeList[i]).before(curSpan);
            $(mathcodeList[i]).remove();
          }
        }
        MathJax.Hub.Queue(["Typeset",MathJax.Hub]);
      }
    }, 1000)
  });
</script>
</div></html>